package 面试经典150题.链表;

import common.TreeNode;

import java.util.HashMap;
import java.util.Map;

/**
 * @author tmh
 * @date 2024/6/30 21:24
 * @description
 */
public class T106从中序与后序遍历序列构造二叉树 {
    //定义一个map 方面根据数值来查找元素的位置
    Map<Integer,Integer> map;
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        map = new HashMap<>();
        //把中序数组里面元素的位置放在map里面
        for (int i=0;i<inorder.length;i++){
            map.put(inorder[i],i);
        }
        //调用这个方法来构造二叉树
        return findNode(inorder,0,inorder.length,postorder,0,postorder.length);

    }

    private TreeNode findNode(int[] inorder, int inBegin, int inEnd, int[] postorder, int postBegin, int postEnd) {
        //1. 判断参数范围是否满足前闭后开
        if(inBegin>=inEnd||postBegin>=postEnd){
            // 不满足左闭右开，说明没有元素，返回空树
            return null;
        }
        //2.找到后续数组里面的最后一个元素在中序遍历中的位置
        Integer rootIndex = map.get(postorder[postEnd - 1]);
        //3.在中序数组里面 用这个rootIndex构造一个节点
        TreeNode root = new TreeNode(inorder[rootIndex]);
        //4.保存中序左子树的个数，用来确定后序数列的个数
        int lenOfLeft = rootIndex-inBegin;
        //遍历左序列  用左闭右开区间来理解就好些范围很多了
        //inorder = [9,3,15,20,7], postorder = [9,15,7,20,3] 可以用这两个数组来大脑里面想象区间划分过程--很有用
        root.left = findNode(inorder,inBegin,rootIndex,postorder,postBegin,postBegin+lenOfLeft);
        //遍历右序列
        root.right = findNode(inorder,rootIndex+1,inEnd,postorder,postBegin+lenOfLeft,postEnd-1);
        return root;
    }
}
